{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Iterators"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`for` loops \"lower\" to `while` loops plus calls to the `iterate` function:\n",
    "\n",
    "```jl\n",
    "for i in iter   # or  \"for i = iter\" or \"for i ∈ iter\"\n",
    "    # body\n",
    "end\n",
    "```\n",
    "\n",
    "internally works the same as:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```jl\n",
    "next = iterate(iter)\n",
    "while next !== nothing\n",
    "    (i, state) = next\n",
    "    # body\n",
    "    next = iterate(iter, state)\n",
    "end\n",
    "```\n",
    "\n",
    "The same applies to comprehensions and generators."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note `nothing` is a singleton value (the only value of its type `Nothing`) used by convention when there is no value to return (a bit like `void` in C). For example "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "typeof(print(\"hello\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = ['a','b','c'];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "iterate(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "iterate(A, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "iterate(A, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "iterate(A, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Iteration is also used by \"destructuring\" assignment:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x, y = A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yet another user of this \"iteration protocol\" is so-called argument \"splatting\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "string(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "string('a','b','c')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "string(A...)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iteration utilities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`collect` gives you all elements of an iterator as an array.\n",
    "Comprehensions are actually equivalent to calling `collect` on a generator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "collect(pairs(A))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "collect(zip(100:102,A))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some other favorites to experiment with. These are in the built-in `Iterators` module:\n",
    "- `enumerate`\n",
    "- `rest`\n",
    "- `take`\n",
    "- `drop`\n",
    "- `product`\n",
    "- `flatten`\n",
    "- `partition`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some iterators are infinite!\n",
    "- `countfrom`\n",
    "- `repeated`\n",
    "- `cycle`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "I = zip(Iterators.cycle(0:1), Iterators.flatten([[2,3],[4,5]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "collect(I)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "collect(Iterators.product(I,A))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "string(I...)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining iterators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "struct SimpleRange\n",
    "    lo::Int\n",
    "    hi::Int\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Base.iterate(r::SimpleRange, state = r.lo) = state > r.hi ? nothing : (state, state+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Base.length(r::SimpleRange) = r.hi-r.lo+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "collect(SimpleRange(2,8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterator traits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For many algorithms, it's useful to know certain properties of an iterator up front.\n",
    "\n",
    "The most useful is whether an iterator has a fixed, known length."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Base.IteratorSize([1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Base.IteratorSize(Iterators.repeated(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Base.IteratorSize(eachline(open(\"/dev/null\")))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Define an iterator giving the first N fibonacci numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Index iterators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = rand(3,5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eachindex(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "keys(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Av = view(A, [1,3], [1,2,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A[[1,3],[1,2,5]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eachindex(Av)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example: $3\\times 3\\times \\dots \\times3$ boxcar filter (from a blog post by Tim Holy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function boxcar3(A::AbstractArray)\n",
    "    out = similar(A)\n",
    "    R = CartesianIndices(size(A))\n",
    "    I1, Iend = first(R), last(R)\n",
    "    for I in R\n",
    "        n, s = 0, zero(eltype(out))\n",
    "        for J in CartesianIndices(map(:, max(I1, I-I1).I, min(Iend, I+I1).I))\n",
    "            s += A[J]\n",
    "            n += 1\n",
    "        end\n",
    "        out[I] = s/n\n",
    "    end\n",
    "    out\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "using Images"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = rand(256,256);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Gray.(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Gray.(boxcar3(A))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function sumalongdims!(B, A)\n",
    "    # It's assumed that B has size 1 along any dimension that we're summing\n",
    "    fill!(B, 0)\n",
    "    Bmax = CartesianIndex(size(B))\n",
    "    for I in CartesianIndices(size(A))\n",
    "        B[min(Bmax,I)] += A[I]\n",
    "    end\n",
    "    B\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "B = zeros(1, 256)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sumalongdims!(B, A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "reduce(+,A,dims=(1,))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`CartesianIndices` and other \"N-d\" iterators have a shape that propagates through generators."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[1 for i in CartesianIndices((2,3))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "B = rand(5,5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "view(B,CartesianIndices((2,3)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise: CartesianIndex life!\n",
    "\n",
    "- Write a function `neighborhood(A::Array, I::CartesianIndex)` that returns a view of the 3x3 neighborhood around a location\n",
    "- Write a function `liferule(A, I)` that implements the evolution rule of Conway's life cellular automaton:\n",
    "  - 2 live neighbors $\\rightarrow$ stay the same\n",
    "  - 3 live neighbors $\\rightarrow$ 1\n",
    "  - otherwise $\\rightarrow$ 0\n",
    "- Write a function `life(A)` that maps A to the next life step using these"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some famous initial conditions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = fill(0, 128,128);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A[61:63,61:63] = [1 1 0\n",
    "                  0 1 1\n",
    "                  0 1 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = life(A)\n",
    "# `repeat` can be used to get chunky pixels to make the output easier to see\n",
    "Gray.(repeat(A,inner=(4,4)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "kernelspec": {
   "display_name": "Julia 1.1.0-DEV",
   "language": "julia",
   "name": "julia-1.1"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.0.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
